The present invention is related to architectures and related structures used for computer network routing tables and, in particular, for PNNI routing tables used in ATM networks.
Asynchronous Transfer Mode (ATM) is a connection oriented system. As such, connection requests need to be routed from a requesting node though the ATM network to a destination node. The ATM Forum has defined a private network-to-network or node-to-node interface (PNNI) protocol which allows easier interconnection of ATM switches. The PNNI protocol consists of two components. The first is a signaling protocol used to relay ATM connection requests within a network between a source and a destination. The second is a routing protocol used to determine the path for routing signaling requests though the ATM network. The goal of the PNNI protocol is to advertise enough information between the nodes of a network so as to allow the nodes to route call requests within the network. Ideally, every ATM switch in a network would not only know the address of every ATM attached installation but also the current available composite (VPI/VCI) for new switched virtual circuits (SVCs) to every switch. However, as ATM networks grow to include hundreds or even thousands of switches supporting tens of thousands of users and devices, such an implementation becomes unfeasible.
Nevertheless, finding the shortest or best available path from one point to another across an ATM network does require that each node know something about what the network looks like. For example, each node must know its own whereabouts in the network and be able to locate other nodes or ATM installations so that it can establish virtual circuits offering the appropriate speed and quality of service (QoS) parameters. The solution devised by the ATM Forum is a scheme that distributes and summarizes network topologies so that nodes have detailed information about their local topology and summarized information about more distant regions of the network. The PNNI protocol manages this information through the use of.an hierarchical topology, along with an addressing scheme similar to that used in telephony networks.
For each node (e.g., switch) of an ATM network, a PNNI interface associates a connection between two nodes and the connection may be a physical link or a virtual path connection (VPC). In general, every PNNI-capable node has several such interfaces and each is associated with a set of parameter (usually stored in a data structure in memory), including a traffic metrics table that stores the available traffic resource parameters on the link associated with the interface (in the forward direction). These traffic metric""s tables are generally two-dimensional and associate service classes with the type of traffic metrics or attributes supported by the connection. In one sense, PNNI is a link state algorithm and QoS-based routing protocol which can collect and advertise these link state parameters (i.e., the attributes and metrics that are associated with each link and node) which become the bases for routing path selections within the network.
Using PNNI, then network nodes are provided with xe2x80x9creachability informationxe2x80x9d (i.e., based on the traffic metrics and attributes) about other nodes. This reachability information is used by a source node to construct a designated transit list (DTL) that describes a complete route to a destination node. The DTL is inserted into a signaling request which is then transmitted along the path described by the DTL. Thus, using PNNI, a single connection will be set up between the source node and the destination node.
ATM nodes configured to use the PNNI routing protocol advertise the reachability of a particular ATM address over multiple ATM physical links. The various levels of the switching hierarchy established by PNNI, map different segments of the overall ATM network in different degrees of detail. By breaking a large network of ATM switches into smaller domains called peer groups, PNNI allows individual switches to navigate paths through the entire network without requiring them to store an entire map of the network in memory. PNNI organizes nodes into peer groups and nodes within a peer group elect a leader node called a peer group leader. The peer group leader summarizes information about the peer group and presents that information to the next higher level hierarchy and also instantiates a logical group node (LGN) at the next higher level. The LGN represents its own child peer group at the lower level and becomes the peer of other LGNs at its level.
Using PNNI then, nodes in an ATM network automatically form a hierarchy of peer groups according to addresses assigned by a network manager. The nodes"" ATM addresses provide the key to the structure of this hierarchy. Each peer group has its own identifier (called a peer group ID), similar to a telephone exchange or area code. For a lower level peer group this ID is similar to an area code and exchange. For a higher peer group, it would be similar to just the area code. Finally, each node within a peer group has a unique address, similar to the way each line in a telephone exchange has a unique number.
Once the PNNI hierarchy is created, peer group leaders are allocated, and routing information is exchanged. Thereafter, the ATM nodes can begin to establish SVCs between various end-stations on the network. Using the PNNI protocol, installations on remote networks can easily establish SVCs across the hierarchy with other end stations and different peer groups.
When a signaling request is received across a user-to-network interface (UNI) by a ingress node, the node will use a shortest path algorithm, such as a Dijkstra calculation, to determine a path to connect the call to the desired destination. This calculation will create a set of DTLs, and each node will have: a full, detailed path within the source node""s own peer group; a less detailed path within the parent peer groups; and even less detail on higher level peer groups, terminating in the lowest level peer group which is an ancestor of both the source and the destination nodes. Hence, using PNNI, SVCs can be set up across a network. Once the connection is established, ATM cells are forwarded by simple table lookups, e.g., using connection tables.
As indicated above, the PNNI specification requires that QoS sensitive source routing algorithms be used in the PNNI hierarchical routing environment. QoS sensitive routing implies that the route selection algorithm must determine whether a source route can support all of the QoS requirements of a request. This requires that the routing algorithm consider both link constraints and path constraints. Link constraints such as available bandwidth (AvCR) are relatively easy to deal with because links which do not meet a caller""s requirements may simply be dropped or pruned from the topology during the shortest path calculation. However, path constraints such as cell transfer delay (CTD) and cell delay variation (CDV) are more difficult to deal with because they are not dependent on a single link only and, to date, no known routing algorithm is capable of optimizing for multiple path constraints.
Of the known routing algorithms (or shortest path algorithms), on-demand routing has gained some popularity. Indeed, one method of on-demand routing is presented as an appendix to the ATM Forum""s PNNI specification. In general, on-demand routing performs a separate route computation for each requested route. On-demand routing according to this method optimizes on a single path constraint while pruning links that do not meet the caller""s requirements.
Another routing scheme proposed in the PNNI specification uses pre-computed routes. In this case, sets of paths for each QoS (e.g., constant bit rate (CBR), real-time variable bit rate (rtVBR), non-real-time variable bit rate (nrtVBR), available bit rate (ABR) and unspecified bit rate (UBR)) are pre-calculated by computing the shortest path routes using a single optimization criteria for a single class of service. The routes provided are optimized without considering bandwidth (i.e., so long as a link has  greater than 0 bandwidth it is used for the shortest path computation) and the method falls back to on-demand routing every time the search of pre-computed routes fails. In general, the pre-computed routes are stored in linear routing tables. The number of pre-calculated routing tables depends on the number of combinations of QoS-based link state parameters that a node generates and receives from the network. Each routing table is maintained as a shortest path tree (SPT), and each SPT is constructed based on the optimization of a single traffic metric. In other words, each SPT maintains a shortest path tree to each reachable destination node in the same PNNI routing domain based on a single criterion, i.e., a traffic metric.
The use of such conventional routing tables, however, has several undesirable effects. For example, because the shortest path information is maintained as a linear table, and because usually multiple such tables are required to accommodate all of the various traffic metrics and service classes, a considerable amount of memory is required just to store the tables. Indeed, where all service classes exist in a network, a maximum number of these tables may have to be generated and stored. Further, because known routing algorithms can only optimize on a single constraint at a time, this suggests that any SPT made up of traditional routing tables will contain only those paths optimized for the designated traffic parameter. Yet, other parameters (which were not the subject of the route optimization computation) may also be determinative of whether a given route may be used by a connection request.
What is desired, therefore, is a routing table structure for ATM or other networks that avoids the drawbacks of prior schemes.
The present invention provides an improved routing table structure for ATM or other networks which, in one embodiment, comprises a shortest path tree architected and organized as a pseudo-spanning tree. The pseudo-spanning tree is a graphical representation of computed routes within the network, optimized to a specified constraint for a specified network service category, and allows for rapid compilation of one or more source-computed routes (e.g., DTLs in an ATM network) by traversing from a destination node specified in a call request to the calculating node (i.e., the node at which the request is received). Unlike conventional spanning trees, however, the pseudo-spanning tree representation may include alternate routes between network nodes. By providing these alternate routes in a single routing table structure, the present invention may utilize less storage and processing resources as compared to routing table schemes of the past. Further, in addition to the single optimization criterion, the routing table structure includes other network traffic parameters for associated links and nodes of the network.
In a further embodiment, the present invention provides a computer-generated shortest path tree which includes a graphical representation of one or more inter-nodal paths in a computer network, optimized to a specified constraints. In general, the constraints may be an ATM traffic parameter, for example a delay-based constraints or a cost-based constraints. The graphical representation may comprise a tree structure, made up of root node (i.e., the node which generated the tree), one or more branch nodes and/or one or more leaf nodes. The leaf nodes are characterized as having at least one parent node, which may be a branch node or the root node, and no child nodes. The branch nodes are characterized by having at least one parent node, which may be another branch node or the root node, and at least one child node, which may be another branch node or a leaf node. The root node is characterized by not having any parent nodes. The various nodes of the tree are connected by one or more links of the computer network. Where a child node has two or more parent nodes in the graphical representation, this is an indication that two equal cost paths exist within the computer network to reach the node represented by that child root.
In yet a further embodiment, the present invention provides a method which includes generating a shortest path tree as a graphical representation of one or more inter-nodal paths in a computer network, optimized to a specified constraints (e.g., an ATM traffic parameter). Prior to generating the shortest path tree, the constraints may be selected, and the constraint may be a delay- or cost-based constraint (e.g., the relative desirability of using a link within the computer network). Further, in response to a connection request, one of the paths may be selected, for example by tracing the inter-nodal paths from a destination node identified in the request to a local node. The destination node may be selected using an index pointer from a table accessed using the information from the request.